Abstract: Local search meta-heuristic algorithm (LSM) is the meta-heuristic approximate problems solving method used to solve real world complex problems and those problems, which come in under NP-Hard category. The drawback of using the exact algorithm (e.g., Branch and Bound) is that its computation time increases exponentially when input size is increased. Therefore, meta-heuristic algorithm significantly reduces the search space size to be explored and also the time required to search it. Although LSM finds near- optimal solution in very optimum time compared to the exact algorithm, its computation time increases when the size of input increased beyond some limit. Therefore, General Purpose Graphics Processing Units (GPGPU) based parallel computing is the best alternate way to speed up the search task. Moreover, GPGPU based computing for LSM is rarely investigated and analyzed. This paper gives detailed information about local searching strategy to solve optimization problem on GPU based computing.

Keywords: Exact algorithm, Local search meta-heuristic, GPGPU computing.